#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <crtdbg.h>

int* calculate_prefix(const char* str, int n) {
	
	const int str_len = n;
	int* prefix = (int*) malloc(str_len*sizeof(int));

	if(str_len == 0)
		return prefix;

	prefix[0] = 0;

	for(int current = 1; current < str_len; ++current) {
		int matched_prefix = current - 1;
		int candidate = prefix[matched_prefix];

		while(candidate != 0 && str[current] != str[candidate]) {
			matched_prefix = prefix[matched_prefix] - 1;
			candidate = prefix[matched_prefix];
		}

		if(candidate == 0)
			prefix[current] = str[current] == str[0] ? 1 : 0;
		else
			prefix[current] = candidate + 1;
	}
	return prefix;
}

char* concat(const char* str1, const char* str2, const char separator = '\0') {
	const int len1 = strlen(str1);
	const int len2 = strlen(str2);

	char* output = (char*) malloc((len1+len2+1)*sizeof(char));

	int i;
	for(i = 0; i < len1; i++) {
		output[i] = str1[i];
	}
	output[len1] = separator;
	for(i = 0; i < len2; i++) {
		output[len1+i+1] = str2[i];
	}

	return output;
}

void main() {
	int i;
	int n;

	char* str		= (char*) malloc(511*sizeof(char));
	char* pattern	= (char*) malloc(255*sizeof(char));
	char* output;

	int* prefix;

	printf("enter a text:\n");
	scanf("%s", str);
	printf("\n");

	printf("enter a pattern:\n");
	scanf("%s", pattern);
	printf("\n\n");
	
	n = strlen(str) + strlen(pattern) +1;
	output = concat(pattern, str, '\0');

	prefix = calculate_prefix(output,n);

	bool found = false;
	for(i = 0; i < n; i++) {
		if(prefix[i] == strlen(pattern)) {
			int index = i - strlen(pattern)*2;
			found = true;
			printf("match has been found at %d\n", index+1);
		}
	}
	if(!found)
		printf("no matches has been found\n");

	printf("\n");
	system("pause");

	free(str);
	free(pattern);
	free(output);
	free(prefix);

	_CrtDumpMemoryLeaks();
}